//
// Created by Administrator on 2021/5/25.
//
#include <queue>
#include <iostream>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
private:
    int maxDepth = 0;
    int ans = 0;
public:
    int deepestLeavesSum(TreeNode *root) {
        // 一次遍历找到最大深度
        findMaxDepth(root, 0);
        // 一次遍历找到深度最大的叶子之和
        getLeavesSum(root, 0);
        return ans;
    }

    void findMaxDepth(TreeNode *root, int depth) {
        if (root == nullptr) return;
        maxDepth = max(maxDepth, depth);
        findMaxDepth(root->left, depth + 1);
        findMaxDepth(root->right, depth + 1);
    }

    void getLeavesSum(TreeNode *root, int curDepth) {
        if (root == nullptr) return;
        if (curDepth == maxDepth) {
            ans += root->val;
            return;
        }
        getLeavesSum(root->left, curDepth + 1);
        getLeavesSum(root->right, curDepth + 1);
    }
};

class Solution2 {
private:
    int maxDep = -1;
    int total = 0;

public:
    void dfs(TreeNode *node, int dep) {
        if (!node) {
            return;
        }
        if (dep > maxDep) {
            maxDep = dep;
            total = node->val;
        } else if (dep == maxDep) {
            total += node->val;
        }
        dfs(node->left, dep + 1);
        dfs(node->right, dep + 1);
    }

    int deepestLeavesSum(TreeNode *root) {
        // 只一次遍历，在遍历过程中修改
        dfs(root, 0);
        return total;
    }
};
using PTI = pair<TreeNode*, int>;

class Solution3 {
public:
    int deepestLeavesSum(TreeNode* root) { //bfs
        queue<PTI> q;
        q.emplace(root, 0);   // 队列中储存的是节点和深度
        int maxdep = -1, total = 0;
        while (!q.empty()) {
            TreeNode* node = q.front().first;
            int dep = q.front().second;
            q.pop();
            if (dep > maxdep) {
                maxdep = dep;
                total = node->val;
            }
            else if (dep == maxdep) {
                total += node->val;
            }
            if (node->left) {
                q.emplace(node->left, dep + 1);
            }
            if (node->right) {
                q.emplace(node->right, dep + 1);
            }
        }
        return total;
    }
};


int main() {
    auto n1 = TreeNode(1), n2 = TreeNode(2), n3 = TreeNode(3), n4 = TreeNode(4), \
 n5 = TreeNode(5), n6 = TreeNode(6), n7 = TreeNode(7), n8 = TreeNode(8);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.right = &n6;
    n4.left = &n7;
    n6.right = &n8;
    Solution sol;
    cout << sol.deepestLeavesSum(&n1) << endl;
    return 0;
}